package q870_advantageCount;

import java.util.Arrays;

public class Solution_1 {
    /*
    优势洗牌
    比较容易理解的一种解法：田忌赛马模式
    首先对nums1排序
    然后将nums2的值-序号对存储到一个二维数组中，
    接下来通过双指针的方式开始考虑，如果当前i位置的值能够大于nums2的left
    那么就将其放入ans，否则操作右指针
     */
    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        int len = nums1.length;
        int[][] new_nums2 = new int[len][2];
        for (int i = 0; i < len; i++) {
            new_nums2[i][0] = nums2[i];
            new_nums2[i][1] = i;
        }
        Arrays.sort(new_nums2, (a, b) -> a[0] - b[0]);
        int[] ans = new int[len];
        int left = 0, right = len - 1;
        for (int i = 0; i < len; i++) {
            if (nums1[i] > new_nums2[left][0]) {
                ans[new_nums2[left][1]] = nums1[i];
                left++;
            } else {
                ans[new_nums2[right][1]] = nums1[i];
                right--;
            }
        }
        return ans;
    }
}
